package com.mango.leet.code.week1.game387;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * https://leetcode.cn/contest/weekly-contest-387/problems/count-submatrices-with-top-left-element-and-sum-less-than-k/
 * @Author: mango
 * @Date: 2024/3/10 09:57
 */
public class LC3070 {
    List<List<List<Integer>>> res = new LinkedList<>();
    // 记录回溯算法的递归路径
    LinkedList<LinkedList<Integer>> track = new LinkedList<>();

    public int countSubmatrices(int[][] grid, int k) {
        dfs(grid, k, 1, 1);
        System.out.println(res);
        return 0;
    }

    // 回溯算法核心函数，遍历子集问题的回溯树
    void dfs(int[][] nums, int k, int x, int y) {
        if (x == nums.length) {
            return ;
        }
        if (y == nums[0].length) {
            return ;
        }
        // 前序位置，每个节点的值都是一个子集
        res.add(new LinkedList<>(track));

        // 回溯算法标准框架
        for (int i = 0; i <= x; i++) {
            LinkedList<Integer> col = new LinkedList<>();
            for (int j = 0; j <= y; j++) {
                col.addLast(nums[i][j]);
            }

            // 做选择
            track.addLast(col);
            // 通过 start 参数控制树枝的遍历，避免产生重复的子集
            dfs(nums, k, x+1, y);
            dfs(nums, k, x, y+1);
            // 撤销选择
            track.removeLast();

        }
    }
    public static void main(String[] args) {
        int[][] nums = {
                {1, 2, 3},
                {2, 3, 4}
        };
        LC3070 t = new LC3070();
        t.countSubmatrices(nums, 2);
    }


}
